import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

/**
 * 后缀表达式：  我们常使用的为中缀表达式  5+3*8
 * 计算机更容易实现的后缀表达式： 3 8 * 5 +
 *
 * 步骤--》1.先将中缀表达式转换成后缀表达式   （将中缀表达式转换成为list集合，通过stack将中缀表达式转换成后缀表达式）
 * 2. 在将后缀表达式进行计算求值
 */
public class PostfixExpression {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入您要计算的表达式：");
        String expression = scanner.nextLine();
        List<String> centerList = AnalyticExpression(expression); //将中缀表达式转换成list集合
        System.out.println("中缀表达式："+centerList.toString());
        List<String> postfixList = toPostfixExpression(centerList); //将中缀集合转换成后缀表达式集合
        System.out.println("后缀表达式："+postfixList.toString());
        int res = calculator(postfixList);
        System.out.println(res);
    }


    /**
     * 将字符串转换成字符串集合
     *
     * @param expression 传过来的字符串后缀表达式
     * @return 返回的字符串集合
     */
    public static List<String> AnalyticExpression(String expression) {

        List<String> list = new ArrayList<>();
        char c;
        String str = "";  //用于拼接多位数
        int i = 0;
        while (i < expression.length()) {
            if ((c = expression.charAt(i)) < 48 || (c = expression.charAt(i)) > 57) {//如果不是数字
                list.add(c + "");
                i++;
            } else {
                str = "";
                while (i < expression.length() && ((c = expression.charAt(i)) >= 48) && ((c = expression.charAt(i)) <= 57)) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        }
        return list;
    }

    /**
     * 将中缀表达式转换成后缀表达式
     * 思路：
     * 1）初始化两个栈，运算符栈s1和储存中间结果的栈s2
     * 2）从左至右扫描中缀表达式
     * 3）遇到操作数时，将其压入s2
     * 4）遇到运算符时，比较其与s1栈顶运算符的优先级
     * 4.1 如果s1为空，或栈顶运算符为左括号 "(" ，则直接将此运算符入s1栈
     * 4.2 否则，若优先级比s1栈顶运算符的高，也将运算符压入s1
     * 4.3 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到4.1与s1中新的栈顶运算符相比较
     * 5)遇到括号时：
     * (1) 如果是左括号 "(" 。则直接压入s1
     * (2) 如果是右括号 ")" 。则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃。
     * 6)重复步骤2至5直到表达式的最右边
     * 7)将s1中剩余的运算符依次弹出并压入s2
     *
     * @param centerList
     * @return
     */
    public static List<String> toPostfixExpression(List<String> centerList) {
        Stack<String> s1 = new Stack<>();
        Stack<String> s2 = new Stack<>();
        List<String> list = new ArrayList<>();
        List<String> list1 = new ArrayList<>();
        int i = 0;
        while (i < centerList.size()) {
            if (centerList.get(i).matches("\\d+")) { //如果是数字
                s2.push(centerList.get(i));
                i++;
            } else if (centerList.get(i).equals("*") || centerList.get(i).equals("/")||centerList.get(i).equals("+")||centerList.get(i).equals("-")) { // 如果是运算符
                if (s1.empty() || s1.peek().equals("(")) {   // 符合4.1
                    s1.push(centerList.get(i));
                    i++;
                } else if (getLevel(centerList.get(i)) > getLevel(s1.peek())) { // 符合4.2
                    s1.push(centerList.get(i));
                    i++;
                } else {
                    s2.push(s1.pop());
                }
            } else {// 为括号
                if (centerList.get(i).equals("(")) {
                    s1.push(centerList.get(i));
                    i++;
                } else if (centerList.get(i).equals(")")) {
                    while (!s1.peek().equals("(")) {
                        s2.push(s1.pop());
                    }
                    s1.pop();
                    i++;
                }
            }
        }

        //将s1剩余的运算符依次弹出并压入s2
        while (!s1.empty()){
            s2.push(s1.pop());
        }

        while (!s2.empty()){
            list.add(s2.pop());
        }

        for (int j = list.size()-1; j >= 0; j--) {
            list1.add(list.get(j));
        }
        return list1;
    }

    /**
     *
     * @param list
     * @return
     */
    public static int calculator(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String s : list) {
            if (s.matches("\\d+")) {//如果是数字的话，直接入栈
                stack.push(s);
            } else { // 是符号的话，就pop出两个元素进行运算然后入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (s.equals("+")) {
                    res = num1 + num2;
                } else if (s.equals("-")) {
                    res = num1 - num2;
                } else if (s.equals("*")) {
                    res = num1 * num2;
                } else if (s.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符异常");
                }
                stack.push("" + res);
            }
        }
        return Integer.parseInt(stack.peek());
    }

    /**
     * 获取运算符的优先级
     *
     * @param str
     * @return 加减 0  乘除 1
     */
    public static int getLevel(String str) {
        int level = 0;
        if (str.equals("*") || str.equals("/")) {
            level = 1;
        }
        return level;
    }
}
